A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information.
Large computer networks, such as the Internet, often include many routers grouped into administrative domains called “autonomous systems.” In order to maintain an accurate representation of the network, routers periodically exchange routing information in accordance with defined protocols. These routing protocols generally fall into two categories. Routers located at the edges of different autonomous systems generally use exterior routing protocols to exchange information. One example of an exterior routing protocol is the Border Gateway Protocol (BGP). Routers within an autonomous system generally utilize interior routing protocols for exchanging routing information. One example of an interior routing protocol is the Intermediate System to Intermediate System (ISIS) protocol, which is an interior gateway routing protocol for IP-based networks. Other examples of interior routing protocols include the Open Shortest Path First (OSPF), and the Routing Information Protocol (RIP).
When two routers initially connect, they typically exchange routing information that describes the routes of which each router is aware. The routers send control messages to incrementally update the routing information when the network topology changes. For example, the routers may send update messages to advertise newly available routes, and to withdraw routes that are no longer available.
Routers operating within different autonomous systems or domains may be aware of, and able to support, vastly different numbers of routes. For example, a router operating within an internet service provider network, i.e., a service provider (SP) router, may exchange routing information with a large number of routers using a variety of routing protocols, including both exterior and interior routing protocols. Consequently, the SP router may be aware of hundreds of thousands or even millions of routes, e.g., routes through the internet service provider network, routes to various customer networks and routes to other service providers.
The SP router, however, is typically configured to communicate only a small subset of these routes to a given router operating within a customer network. Specifically, the SP router only communicates a small percentage of these routes to the customer router via an exterior routing protocol. The customer router may then utilize an interior routing protocol to communicate these routes to other routers within the customer network. This process is often referred to as the “leaking” or “exporting” of routes from an exterior protocol to an interior protocol.